'''
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。
'''


# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if root is None:
            return root
        
        from collections import deque
        q = deque()
        q.append(root)

        while q:
            sz = len(q)

            for i in range(sz):
                p = q.popleft()
                if i < sz - 1:
                    p.next = q[0]
                if p.left:
                    q.append(p.left)
                if p.right:
                    q.append(p.right)
        return root
    
    def connect2(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if root is None:
            return root
        
        leftrecord = root

        while leftrecord.left:
            p = leftrecord
            while p:
                p.left.next = p.right

                if p.next:
                    p.right.next = p.next.left
                
                p = p.next
            
            leftrecord = leftrecord.left
        
        return root

